package com.graphcoloring;

import java.util.Arrays;
import java.util.List;

public class BruteForceSolver implements Solver {
    private GraphInputData data;

    private int colorCount;
    private int colors[];

    private int vertexColors[];

    public Solution solve(GraphInputData data) throws Exception {
        this.data = data;
        vertexColors = new int[data.getVertexNumber()];
        colors = new int[data.getVertexNumber()];

        Arrays.fill(vertexColors, -1);
        for (int k = data.getVertexNumber(); k >= 1; k--) {
            if (paintVertex(0, k)) {
                colorCount = k;
                for (int i = 0; i < data.getVertexNumber(); i++) colors[i] = vertexColors[i];
            } 
            else break;
        }
        Solution solution = new Solution();
        solution.colorCount = colorCount;
        solution.colors = colors;
        return solution;

    }

    private boolean paintVertex(int vertex, int maxcolor) {
        if (vertex == data.getVertexNumber())
            return true;

        List<Integer> adjacentVertices = data.getConnectedEdges().get(vertex);
        for (int i = 0; i < maxcolor; i++) {
            boolean canPaint = true;
            for (int adjacentVertice : adjacentVertices) {
                if (vertexColors[adjacentVertice] == i) {
                    canPaint = false;
                }
            }
            if (canPaint) {
                vertexColors[vertex] = i;
                if (paintVertex(vertex + 1, maxcolor))
                    return true;
                vertexColors[vertex] = -1;
            }
        }

        return false;
    }
}
